package com.freedy.algorithm.dijkstra;

import java.util.Arrays;

/**
 * @author Freedy
 * @date 2021/4/14 12:00
 */
public class VisitedVertex {
    // 记录各个顶点是否访问过 1 表示访问过,0 未访问,会动态更新
    private int[] already_arr;
    // 每个下标对应的值为前一个顶点下标, 会动态更新
    private int[][] paths;
    // 记录出发顶点到其他所有顶点的距离,比如 G 为出发顶点，就会记录 G 到其它顶点的距离，
    // 会动态更新，求 的最短距离就会存放到 dis
    private int[] dis;

    /**
     * @param length 顶点的个数
     * @param index 出发顶点对应的下标
     */
    public VisitedVertex(int length,int index) {
        this.already_arr=new int[length];
        this.paths=new int[length][length];
        for (int i = 0; i < length; i++) {
            for (int j = 0; j < length; j++) {
                paths[i][j]=-1;
                paths[i][0]=index;
            }
        }
        this.dis=new int[length];
        Arrays.fill(dis,Integer.MAX_VALUE);
        this.dis[index]=0;
    }

    /**
     * 判断index是否被访问过
     */
    public boolean isVisited(int index){
        return already_arr[index]==1;
    }

    /**
     * 更新距离
     */
    public void updateDis(int index,int len){
        dis[index]=len;
    }


    /**
     * @param index  正在遍历的
     * @param des 要被修改的
     */
    public void updatePaths(int index,int des){
        int top=-1;
        for (int i = 0; i < paths[index].length&&paths[index][i]!=-1; i++) {
            top=i;
        }
        Arrays.fill(paths[des],-1);
        System.arraycopy(paths[index],0,paths[des],0,top+1);
        paths[des][top+1]=des;
    }

    /**
     * 继续选择并返回新的访问顶带
     */
    public int updateArr(){
        int min=Integer.MAX_VALUE;
        int index=0;
        for (int i = 0; i < already_arr.length; i++) {
            if (already_arr[i]==0&&dis[i]<min){
                min=dis[i];
                index=i;
            }
        }
        //更新index顶点被访问过
        already_arr[index]=1;
        return index;
    }

    /**
     * 返回触发顶点到index顶点的距离
     */
    public int getDis(int index){
        return dis[index];
    }

    public int[][] getPaths() {
        return paths;
    }

    public int[] getDis() {
        return dis;
    }
}
